#include "main/utils.h"
using namespace std;

int pathNumCore(int row, int col, vector<vector<int>>& dp) {
  if (dp[row][col] == 0) {
    if (row == 0 || col == 0) {
      dp[row][col] = 1;
    } else {
      dp[row][col] = pathNumCore(row - 1, col, dp) + pathNumCore(row, col - 1, dp);
    }
  }
  return dp[row][col];
}

int pathNum1(const int& rows, const int& cols) {
  vector<vector<int>> dp;
  dp.resize(rows);
  for (int i = 0; i < rows; ++i) {
    dp[i].resize(cols, 0);
  }
  return pathNumCore(rows - 1, cols - 1, dp);
}

int pathNum2(const int& rows, const int& cols) {
  vector<vector<int>> dp;
  dp.resize(rows);
  for (int i = 0; i < rows; ++i) {
    dp[i].resize(cols, 1);
  }
  for (int i = 1; i < rows; ++i) {
    for (int j = 1; j < cols; ++j) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }
  return dp[rows - 1][cols - 1];
}

int pathNum3(const int& rows, const int& cols) {
  vector<int> dp(cols, 1);
  for (int i = 1; i < rows; ++i) {
    for (int j = 1; j < cols; ++j) {
      dp[j] = dp[j] + dp[j - 1];
    }
  }
  return dp[cols - 1];
}

int main() {
  cout << pathNum1(3, 3) << endl;
  cout << pathNum2(3, 3) << endl;
  cout << pathNum3(3, 3) << endl;

  return 0;
}
